<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.1.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.0.0/css/all.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/themes/green/pace-theme-minimal.css">
  <script src="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/pace.min.js" integrity="sha256-gqd7YTjg/BtfqWSwsJOvndl0Bxc8gFImLEkXQT8+qj0=" crossorigin="anonymous"></script>

<script class="next-config" data-name="main" type="application/json">{"hostname":"liukairui.me","root":"/","images":"/images","scheme":"Muse","darkmode":false,"version":"8.10.1","exturl":false,"sidebar":{"position":"left","display":"hide","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":true,"pangu":true,"comments":{"style":"tabs","active":"valine","storage":true,"lazyload":false,"nav":null,"activeClass":"valine"},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta name="description" content="原题来自2020牛客寒假算法基础集训营4，作以存档备查">
<meta property="og:type" content="article">
<meta property="og:title" content="2020牛客寒假算法基础集训营4题解">
<meta property="og:url" content="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A54%E9%A2%98%E8%A7%A3/">
<meta property="og:site_name" content="LiuKairui Website">
<meta property="og:description" content="原题来自2020牛客寒假算法基础集训营4，作以存档备查">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-10-30T16:00:11.000Z">
<meta property="article:modified_time" content="2021-10-18T06:44:13.580Z">
<meta property="article:author" content="Liu Kairui">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="牛客">
<meta property="article:tag" content="ACM">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A54%E9%A2%98%E8%A7%A3/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A54%E9%A2%98%E8%A7%A3/","path":"article/2020牛客寒假算法基础集训营4题解/","title":"2020牛客寒假算法基础集训营4题解"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>2020牛客寒假算法基础集训营4题解 | LiuKairui Website</title>
  

  <script src="/js/third-party/analytics/baidu-analytics.js"></script>
  <script async src="https://hm.baidu.com/hm.js?ea07bceb8f5fa721da2ebf01833faa32"></script>



<div class="nindexBK">
<div class="nindexBKC"></div>
<div class="nindex">
  <h1>Hey👋</h1>
  <p style="font-weight: 500; font-size: 2.2em">欢迎访问Liu Kairui的个人站.</p>
  <p>
      我是一个来自重庆的在校大学生, 偏爱于前端技术<!--与OS设计-->, 偶尔使用 JS / Go 进行轻量项目开发, 欢迎访问我的
      <a href="https://github.com/KairuiLiu" target="_blank"><i class="fab fa-github-alt"></i> GitHub</a> .
  </p>
  <p>
      这个网站主要用来存储学习 / 瞎搞的笔记, 同时提供了邮件、图床等服务. 对于一些自认为有趣的<a href="javascript:;" id="myProj">项目</a>, 我也会将项目介绍, 文档, 甚至是设计指南发布在这里.
  </p>
  <ul>
    <li><p><a href="/artrank/" target="_blank">ArtRank</a>: 基于Node.JS的PageRank文献管理推荐系统</p></li>
    <li><p><a href="/gooj/" target="_blank">GoOJ</a>: 基于Golang的高校在线评测系统</p></li>
    <li><p><a href="/projects/" target="_blank">更多 <i class="fas fa-angle-right"></i></a></p></li>

  </ul>
  <p>
      可以在这些平台找到我: 
      <a href="https://www.zhihu.com/people/liu-kai-rui-18" target="_blank">知乎</a>,
      <a href="https://space.bilibili.com/33238144" target="_blank">bilibili</a>
      和
      <a href="https://www.coolapk.com/u/805314?from=qr" target="_blank">酷安</a>.
  </p>

  <p>
      下滑即可进入博客 <i class="fas fa-arrow-down"></i>
  </p>
</div>
</div>  

 
<script>
  var OriginTitile = document.title;
  var titleTime;
  document.addEventListener("visibilitychange", function() {
    if (document.hidden) {
      document.title = "谢谢离开 | " + OriginTitile;
      clearTimeout(titleTime);
    } else {
      document.title = "欢迎归来 | " + OriginTitile;
      titleTime = setTimeout(function() {
        document.title = OriginTitile;
      }, 2000);
    }
  });
</script>


<script>
  function checkIndex(){
    let nindexItems = [[".nindexBK","display","block","none"],[".headband","display","none","block"],["div.toggle.sidebar-toggle","visibility","hidden","visible"]]; // ,["button.darkmode-toggle","visibility","hidden","visible"]];
    let isIndex = new RegExp("^(\/){0,1}(index){0,1}(\.html){0,1}(/)*$").test(location.pathname);
    let backCanvas = document.querySelector(".nindexBK");
    nindexItems.dispShift = function (stat){this.forEach((e) => {try{document.querySelector(e[0]).style[e[1]]=e[2+stat];}catch{}})}
    if(isIndex){
      nindexItems.dispShift(0);
      window.onscroll=function(){
        if(document.documentElement.scrollTop>backCanvas.offsetHeight*1.05){
          nindexItems.dispShift(1);window.onscroll=null;
        }
      }
      document.querySelector("#myProj").onclick=()=>{
        let projlist = document.querySelector(".nindex>ul");
        projlist.className.indexOf("ulactive")==-1?projlist.classList.add("ulactive"):projlist.classList.remove("ulactive")
      }
    }else nindexItems.dispShift(1);
  }
  checkIndex();
</script>

<!--<script src="https://sdk.jinrishici.com/v2/browser/jinrishici.js" charset="utf-8"></script>-->

  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
<link rel="alternate" href="/atom.xml" title="LiuKairui Website" type="application/atom+xml">
<style>.darkmode--activated{--body-bg-color:#282828;--content-bg-color:#333;--card-bg-color:#555;--text-color:#ccc;--blockquote-color:#bbb;--link-color:#ccc;--link-hover-color:#eee;--brand-color:#ddd;--brand-hover-color:#ddd;--table-row-odd-bg-color:#282828;--table-row-hover-bg-color:#363636;--menu-item-bg-color:#555;--btn-default-bg:#222;--btn-default-color:#ccc;--btn-default-border-color:#555;--btn-default-hover-bg:#666;--btn-default-hover-color:#ccc;--btn-default-hover-border-color:#666;--highlight-background:#282b2e;--highlight-foreground:#a9b7c6;--highlight-gutter-background:#34393d;--highlight-gutter-foreground:#9ca9b6}.darkmode--activated img{opacity:.75}.darkmode--activated img:hover{opacity:.9}.darkmode--activated code{color:#69dbdc;background:0 0}button.darkmode-toggle{z-index:9999}.darkmode-ignore,img{display:flex!important}</style></head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">LiuKairui Website</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">要有信仰</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li>
        <li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li>
        <li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fas fa-hashtag fa-fw"></i>标签</a></li>
        <li class="menu-item menu-item-收藏夹"><a href="/favorites/" rel="section"><i class="fab fa-gratipay fa-fw"></i>收藏夹</a></li>
        <li class="menu-item menu-item-留言板"><a href="/messageBoard/" rel="section"><i class="fab fa-facebook-messenger fa-fw"></i>留言板</a></li>
        <li class="menu-item menu-item-项目"><a href="/projects/" rel="section"><i class="fa fa-satellite fa-fw"></i>项目</a></li>
        <li class="menu-item menu-item-图床"><a href="http://img.liukairui.me/" rel="noopener" target="_blank"><i class="fa fa-bed fa-fw"></i>图床</a></li>
        <li class="menu-item menu-item-云ide"><a href="http://vsc.liukairui.me/" rel="noopener" target="_blank"><i class="fas fa-code fa-fw"></i>云IDE</a></li>
        <li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a></li>
        <li class="menu-item menu-item-邮箱"><a href="http://mail.liukairui.me/mail" rel="noopener" target="_blank"><i class="fas fa-envelope-open-text fa-fw"></i>邮箱</a></li>
        <li class="menu-item menu-item-rss"><a href="/atom.xml" rel="section"><i class="fa fa-rss fa-fw"></i>RSS</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#a%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97"><span class="nav-number">1.</span> <span class="nav-text">A：欧几里得</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#b%E6%8B%AC%E5%8F%B7%E5%BA%8F%E5%88%97"><span class="nav-number">2.</span> <span class="nav-text">B：括号序列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#c%E5%AD%90%E6%AE%B5%E4%B9%98%E7%A7%AF"><span class="nav-number">3.</span> <span class="nav-text">C：子段乘积</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#d%E5%AD%90%E6%AE%B5%E5%BC%82%E6%88%96"><span class="nav-number">4.</span> <span class="nav-text">D：子段异或</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#e%E6%9C%80%E5%B0%8F%E8%A1%A8%E8%BE%BE%E5%BC%8F"><span class="nav-number">5.</span> <span class="nav-text">E：最小表达式</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#f%E6%A0%91%E4%B8%8A%E5%8D%9A%E5%BC%88"><span class="nav-number">6.</span> <span class="nav-text">F：树上博弈</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#g%E9%9F%B3%E4%B9%90%E9%89%B4%E8%B5%8F"><span class="nav-number">7.</span> <span class="nav-text">G：音乐鉴赏</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#h-%E5%9D%90%E7%81%AB%E8%BD%A6"><span class="nav-number">8.</span> <span class="nav-text">H: 坐火车</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#i-%E5%8C%B9%E9%85%8D%E6%98%9F%E6%98%9F"><span class="nav-number">9.</span> <span class="nav-text">I: 匹配星星</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#j-%E4%BA%8C%E7%BB%B4%E8%B7%91%E6%AD%A5"><span class="nav-number">10.</span> <span class="nav-text">J: 二维跑步</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Liu Kairui"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">Liu Kairui</p>
  <div class="site-description" itemprop="description">LiuKairui Persional Website</div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">45</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">24</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author site-overview-item animated">
      <span class="links-of-author-item">
        <a href="https://github.com/KairuiLiu" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;KairuiLiu" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:tclkr@live.com" title="E-Mail → mailto:tclkr@live.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://qm.qq.com/cgi-bin/qm/qr?k=oaf3ToOlN17hr5sHV98bT8qxsNYGaw5L&noverify=0" title="QQ → https:&#x2F;&#x2F;qm.qq.com&#x2F;cgi-bin&#x2F;qm&#x2F;qr?k&#x3D;oaf3ToOlN17hr5sHV98bT8qxsNYGaw5L&amp;noverify&#x3D;0" rel="noopener" target="_blank"><i class="fab fa-qq fa-fw"></i>QQ</a>
      </span>
      <span class="links-of-author-item">
        <a href="/atom.xml" title="RSS → &#x2F;atom.xml"><i class="fa fa-rss fa-fw"></i>RSS</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://liukairui.blog.csdn.net/" title="CSDN → https:&#x2F;&#x2F;liukairui.blog.csdn.net" rel="noopener" target="_blank"><i class="fab fa-cuttlefish fa-fw"></i>CSDN</a>
      </span>
      <span class="links-of-author-item">
        <a href="http://liukairui.cc/" title="国内站点 → http:&#x2F;&#x2F;liukairui.cc" rel="noopener" target="_blank"><i class="fa fa-globe fa-fw"></i>国内站点</a>
      </span>
  </div>
  <div class="cc-license site-overview-item animated" itemprop="license">
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" class="cc-opacity" rel="noopener" target="_blank"><img src="https://cdnjs.cloudflare.com/ajax/libs/creativecommons-vocabulary/2020.11.3/assets/license_badges/small/by_nc_sa.svg" alt="Creative Commons"></a>
  </div>


  <div class="links-of-blogroll site-overview-item animated">
    <div class="links-of-blogroll-title"><i class="fa fa-link fa-fw"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <a href="https://paste.ubuntu.com/" title="https:&#x2F;&#x2F;paste.ubuntu.com&#x2F;" rel="noopener" target="_blank">Ubuntu Pastebin</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://send.firefox.com/" title="https:&#x2F;&#x2F;send.firefox.com&#x2F;" rel="noopener" target="_blank">Firefox Send</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://jkwzs.cn/" title="https:&#x2F;&#x2F;jkwzs.cn&#x2F;" rel="noopener" target="_blank">南花醉笔丶の个人博客</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://ywrby.cn/" title="https:&#x2F;&#x2F;ywrby.cn&#x2F;" rel="noopener" target="_blank">Ywrby个人博客</a>
        </li>
    </ul>
  </div>

        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A54%E9%A2%98%E8%A7%A3/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="Liu Kairui">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LiuKairui Website">
      <meta itemprop="description" content="LiuKairui Persional Website">
    </span>
    
    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="2020牛客寒假算法基础集训营4题解 | LiuKairui Website">
      <meta itemprop="description" content="原题来自2020牛客寒假算法基础集训营4，作以存档备查">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          2020牛客寒假算法基础集训营4题解
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2020-10-31 00:00:11" itemprop="dateCreated datePublished" datetime="2020-10-31T00:00:11+08:00">2020-10-31</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
        </span>
          ，
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95/%E9%A2%98%E8%A7%A3/" itemprop="url" rel="index"><span itemprop="name">题解</span></a>
        </span>
    </span>

  
    <span id="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A54%E9%A2%98%E8%A7%A3/" class="post-meta-item leancloud_visitors" data-flag-title="2020牛客寒假算法基础集训营4题解" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">Valine：</span>
  
    <a title="valine" href="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A54%E9%A2%98%E8%A7%A3/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A54%E9%A2%98%E8%A7%A3/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

<script>
    CONFIG.hostname = location.hostname;
</script>
    <span class="post-meta-break"></span>
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>10k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>9 分钟</span>
    </span>
</div>

            <div class="post-description">原题来自2020牛客寒假算法基础集训营4，作以存档备查</div>
        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h2 id="a欧几里得">A：欧几里得</h2>
<p><img
src="https://img-blog.csdnimg.cn/2020040708251359.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1</span>
<span class="token number">0</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token function">gcd</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">)</span> 由于 b<span class="token operator">=</span><span class="token number">0</span>，不会递归，即是递归<span class="token number">0</span>次。</code></pre>
<hr />
<p>根据样例我们可以尝试写出n=2,3,4...的结果，发现他是斐波那契数列，写一个程序输出斐波那契前100位(long
long)，打表即可</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">long</span> <span class="token keyword">long</span> ans<span class="token punctuation">[</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">&#123;</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token punctuation">,</span><span class="token number">13</span><span class="token punctuation">,</span><span class="token number">21</span><span class="token punctuation">,</span><span class="token number">34</span><span class="token punctuation">,</span><span class="token number">55</span><span class="token punctuation">,</span><span class="token number">89</span><span class="token punctuation">,</span><span class="token number">144</span><span class="token punctuation">,</span><span class="token number">233</span><span class="token punctuation">,</span><span class="token number">377</span><span class="token punctuation">,</span><span class="token number">610</span><span class="token punctuation">,</span><span class="token number">987</span><span class="token punctuation">,</span><span class="token number">1597</span><span class="token punctuation">,</span><span class="token number">2584</span><span class="token punctuation">,</span><span class="token number">4181</span><span class="token punctuation">,</span><span class="token number">6765</span><span class="token punctuation">,</span><span class="token number">10946</span><span class="token punctuation">,</span><span class="token number">17711</span><span class="token punctuation">,</span><span class="token number">28657</span><span class="token punctuation">,</span><span class="token number">46368</span><span class="token punctuation">,</span><span class="token number">75025</span><span class="token punctuation">,</span><span class="token number">121393</span><span class="token punctuation">,</span><span class="token number">196418</span><span class="token punctuation">,</span><span class="token number">317811</span><span class="token punctuation">,</span><span class="token number">514229</span><span class="token punctuation">,</span><span class="token number">832040</span><span class="token punctuation">,</span><span class="token number">1346269</span><span class="token punctuation">,</span><span class="token number">2178309</span><span class="token punctuation">,</span><span class="token number">3524578</span><span class="token punctuation">,</span><span class="token number">5702887</span><span class="token punctuation">,</span><span class="token number">9227465</span><span class="token punctuation">,</span><span class="token number">14930352</span><span class="token punctuation">,</span><span class="token number">24157817</span><span class="token punctuation">,</span><span class="token number">39088169</span><span class="token punctuation">,</span><span class="token number">63245986</span><span class="token punctuation">,</span><span class="token number">102334155</span><span class="token punctuation">,</span><span class="token number">165580141</span><span class="token punctuation">,</span><span class="token number">267914296</span><span class="token punctuation">,</span><span class="token number">433494437</span><span class="token punctuation">,</span><span class="token number">701408733</span><span class="token punctuation">,</span><span class="token number">1134903170</span><span class="token punctuation">,</span><span class="token number">1836311903</span><span class="token punctuation">,</span><span class="token number">2971215073</span><span class="token punctuation">,</span><span class="token number">4807526976</span><span class="token punctuation">,</span><span class="token number">7778742049</span><span class="token punctuation">,</span><span class="token number">12586269025</span><span class="token punctuation">,</span><span class="token number">20365011074</span><span class="token punctuation">,</span><span class="token number">32951280099</span><span class="token punctuation">,</span><span class="token number">53316291173</span><span class="token punctuation">,</span><span class="token number">86267571272</span><span class="token punctuation">,</span><span class="token number">139583862445</span><span class="token punctuation">,</span><span class="token number">225851433717</span><span class="token punctuation">,</span><span class="token number">365435296162</span><span class="token punctuation">,</span><span class="token number">591286729879</span><span class="token punctuation">,</span><span class="token number">956722026041</span><span class="token punctuation">,</span><span class="token number">1548008755920</span><span class="token punctuation">,</span><span class="token number">2504730781961</span><span class="token punctuation">,</span><span class="token number">4052739537881</span><span class="token punctuation">,</span><span class="token number">6557470319842</span><span class="token punctuation">,</span><span class="token number">10610209857723</span><span class="token punctuation">,</span><span class="token number">17167680177565</span><span class="token punctuation">,</span><span class="token number">27777890035288</span><span class="token punctuation">,</span><span class="token number">44945570212853</span><span class="token punctuation">,</span><span class="token number">72723460248141</span><span class="token punctuation">,</span><span class="token number">117669030460994</span><span class="token punctuation">,</span><span class="token number">190392490709135</span><span class="token punctuation">,</span><span class="token number">308061521170129</span><span class="token punctuation">,</span><span class="token number">498454011879264</span><span class="token punctuation">,</span><span class="token number">806515533049393</span><span class="token punctuation">,</span><span class="token number">1304969544928657</span><span class="token punctuation">,</span><span class="token number">2111485077978050</span><span class="token punctuation">,</span><span class="token number">3416454622906707</span><span class="token punctuation">,</span><span class="token number">5527939700884757</span><span class="token punctuation">,</span><span class="token number">8944394323791464</span><span class="token punctuation">,</span><span class="token number">14472334024676221</span><span class="token punctuation">,</span><span class="token number">23416728348467685</span><span class="token punctuation">,</span><span class="token number">37889062373143906</span><span class="token punctuation">,</span><span class="token number">61305790721611591</span><span class="token punctuation">,</span><span class="token number">99194853094755497</span><span class="token punctuation">,</span><span class="token number">160500643816367088</span><span class="token punctuation">,</span><span class="token number">259695496911122585</span><span class="token punctuation">,</span><span class="token number">420196140727489673</span><span class="token punctuation">,</span><span class="token number">679891637638612258</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> t<span class="token punctuation">,</span>n<span class="token punctuation">;</span>
    cin<span class="token operator">>></span>t<span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>t<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        cin<span class="token operator">>></span>n<span class="token punctuation">;</span>
        cout<span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h2 id="b括号序列">B：括号序列</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200407082853218.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token punctuation">&#125;</span><span class="token punctuation">[</span><span class="token punctuation">]</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">Yes</code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token punctuation">(</span><span class="token punctuation">&#123;</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">&#125;</span><span class="token punctuation">)</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">Yes</code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">)</span><span class="token punctuation">]</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">No</code></pre>
<hr />
<p>只需要模拟一个栈即可，遇到左括号时压栈，遇到右括号看可否与栈顶元素相匹配，不匹配直接输出错误，匹配则消去栈顶元素。在输入结束后还要检查栈是否为空，为空证明有左括号未匹配</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;stack></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

stack<span class="token operator">&lt;</span><span class="token keyword">char</span><span class="token operator">></span>s<span class="token punctuation">;</span>
<span class="token keyword">char</span> t<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%c"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>t<span class="token punctuation">)</span><span class="token operator">==</span><span class="token number">1</span><span class="token operator">&amp;&amp;</span>t<span class="token operator">!=</span><span class="token char">'\n'</span><span class="token operator">&amp;&amp;</span>t<span class="token operator">!=</span><span class="token char">'\r'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span><span class="token punctuation">(</span>t<span class="token operator">==</span><span class="token char">'&#123;'</span><span class="token operator">||</span>t<span class="token operator">==</span><span class="token char">'&#125;'</span><span class="token operator">||</span>t<span class="token operator">==</span><span class="token char">'('</span><span class="token operator">||</span>t<span class="token operator">==</span><span class="token char">')'</span><span class="token operator">||</span>t<span class="token operator">==</span><span class="token char">'['</span><span class="token operator">||</span>t<span class="token operator">==</span><span class="token char">']'</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>t<span class="token operator">==</span><span class="token char">'&#123;'</span><span class="token operator">||</span>t<span class="token operator">==</span><span class="token char">'['</span><span class="token operator">||</span>t<span class="token operator">==</span><span class="token char">'('</span><span class="token punctuation">)</span>s<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>t<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>s<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>cout<span class="token operator">&lt;&lt;</span><span class="token string">"No"</span><span class="token punctuation">;</span><span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
            <span class="token keyword">char</span> p<span class="token operator">=</span>s<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token punctuation">(</span>t<span class="token operator">==</span><span class="token char">'&#125;'</span><span class="token operator">&amp;&amp;</span>p<span class="token operator">==</span><span class="token char">'&#123;'</span><span class="token punctuation">)</span><span class="token operator">||</span><span class="token punctuation">(</span>t<span class="token operator">==</span><span class="token char">']'</span><span class="token operator">&amp;&amp;</span>p<span class="token operator">==</span><span class="token char">'['</span><span class="token punctuation">)</span><span class="token operator">||</span><span class="token punctuation">(</span>t<span class="token operator">==</span><span class="token char">')'</span><span class="token operator">&amp;&amp;</span>p<span class="token operator">==</span><span class="token char">'('</span><span class="token punctuation">)</span><span class="token punctuation">)</span>s<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>cout<span class="token operator">&lt;&lt;</span><span class="token string">"No"</span><span class="token punctuation">;</span><span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>s<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>cout<span class="token operator">&lt;&lt;</span><span class="token string">"Yes"</span><span class="token punctuation">;</span>
    <span class="token keyword">else</span> cout<span class="token operator">&lt;&lt;</span><span class="token string">"No"</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h2 id="c子段乘积">C：子段乘积</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200407083650967.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span> <span class="token number">3</span>
<span class="token number">1</span> <span class="token number">2</span> <span class="token number">3</span> <span class="token number">0</span> <span class="token number">8</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">6</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1</span><span class="token operator">*</span><span class="token number">2</span><span class="token operator">*</span><span class="token number">3</span>\mod <span class="token number">998244353</span><span class="token operator">=</span><span class="token number">61</span>∗<span class="token number">2</span>∗<span class="token number">3</span>mod998244353<span class="token operator">=</span><span class="token number">6</span></code></pre>
<hr />
<p>可以使用双指针，但是需要求逆元，所以我直接用线段树求解</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">M</span> <span class="token expression"><span class="token punctuation">(</span><span class="token punctuation">(</span>l<span class="token operator">+</span>r<span class="token punctuation">)</span><span class="token operator">>></span><span class="token number">1</span><span class="token punctuation">)</span></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">LC</span> <span class="token expression"><span class="token punctuation">(</span>p<span class="token operator">&lt;&lt;</span><span class="token number">1</span><span class="token punctuation">)</span></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">RC</span> <span class="token expression"><span class="token punctuation">(</span>LC<span class="token operator">|</span><span class="token number">1</span><span class="token punctuation">)</span></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">int</span> MAX_N<span class="token operator">=</span><span class="token number">200050</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> mod<span class="token operator">=</span><span class="token number">998244353</span><span class="token punctuation">;</span>
<span class="token keyword">long</span> <span class="token keyword">long</span> ss<span class="token punctuation">[</span><span class="token number">4</span><span class="token operator">*</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span>k<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">up</span><span class="token punctuation">(</span><span class="token keyword">int</span> p<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    ss<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token operator">=</span>ss<span class="token punctuation">[</span>LC<span class="token punctuation">]</span><span class="token operator">*</span>ss<span class="token punctuation">[</span>RC<span class="token punctuation">]</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">void</span> <span class="token function">modify</span><span class="token punctuation">(</span><span class="token keyword">int</span> p<span class="token punctuation">,</span><span class="token keyword">int</span> x<span class="token punctuation">,</span><span class="token keyword">int</span> v<span class="token punctuation">,</span><span class="token keyword">int</span> l<span class="token punctuation">,</span><span class="token keyword">int</span> r<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>l<span class="token operator">==</span>r<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        ss<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token operator">+=</span>v<span class="token punctuation">;</span>
        <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">&lt;=</span>M<span class="token punctuation">)</span><span class="token function">modify</span><span class="token punctuation">(</span>LC<span class="token punctuation">,</span>x<span class="token punctuation">,</span>v<span class="token punctuation">,</span>l<span class="token punctuation">,</span>M<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">else</span> <span class="token function">modify</span><span class="token punctuation">(</span>RC<span class="token punctuation">,</span>x<span class="token punctuation">,</span>v<span class="token punctuation">,</span>M<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>r<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">up</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token keyword">int</span> p<span class="token punctuation">,</span><span class="token keyword">int</span> x<span class="token punctuation">,</span><span class="token keyword">int</span> y<span class="token punctuation">,</span><span class="token keyword">int</span> l<span class="token punctuation">,</span><span class="token keyword">int</span> r<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">&lt;=</span>l<span class="token operator">&amp;&amp;</span>r<span class="token operator">&lt;=</span>y<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">return</span> ss<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> res<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">&lt;=</span>M<span class="token punctuation">)</span>res<span class="token operator">=</span>res<span class="token operator">*</span><span class="token function">query</span><span class="token punctuation">(</span>LC<span class="token punctuation">,</span>x<span class="token punctuation">,</span>y<span class="token punctuation">,</span>l<span class="token punctuation">,</span>M<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>M<span class="token operator">&lt;</span>y<span class="token punctuation">)</span>res<span class="token operator">=</span>res<span class="token operator">*</span><span class="token function">query</span><span class="token punctuation">(</span>RC<span class="token punctuation">,</span>x<span class="token punctuation">,</span>y<span class="token punctuation">,</span>M<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>r<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">,</span><span class="token operator">&amp;</span>k<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> t<span class="token punctuation">;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>t<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">modify</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span>i<span class="token punctuation">,</span>t<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> ans<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">+</span>k<span class="token operator">-</span><span class="token number">1</span><span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">long</span> <span class="token keyword">long</span> t<span class="token operator">=</span><span class="token function">query</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span>i<span class="token punctuation">,</span>i<span class="token operator">+</span>k<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
        ans<span class="token operator">=</span>ans<span class="token operator">&lt;</span>t<span class="token operator">?</span>t<span class="token operator">:</span>ans<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    cout<span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h2 id="d子段异或">D：子段异或</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200407083945363.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span>
<span class="token number">1</span> <span class="token number">2</span> <span class="token number">3</span> <span class="token number">2</span> <span class="token number">1</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">2</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">子段 <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">]</span> 和子段 <span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">]</span> 是合法子段。</code></pre>
<hr />
<p>异或运算有自反性<br />
<span class="math display">\[ A^\wedge B ^\wedge B = A \]</span>
运用这个性质我们可以得到<br />
l~r的异或和为：前r的异或和 ^ 前l-1的异或和<br />
所以l~r异或和为0当且仅当 l-1异或和==r-1异或和，所以我们<br />
先计算一个异或和的前缀和<br />
然后要找相同的数字，比较好的方法是<br />
对于前缀数组排序，对于每一个数在左右统计相同的数字个数即可</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">long</span> <span class="token keyword">long</span> s<span class="token punctuation">[</span><span class="token number">200050</span><span class="token punctuation">]</span><span class="token punctuation">,</span>n<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%lld"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%lld"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">^</span>s<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">sort</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span>s<span class="token operator">+</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> ans<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>l<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token comment">// for(int i=0;i&lt;=n;i++)cout&lt;&lt;s[i]&lt;&lt;" * ";</span>
    <span class="token comment">// cout&lt;&lt;endl;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>l<span class="token operator">&lt;=</span>n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">long</span> <span class="token keyword">long</span> r<span class="token operator">=</span><span class="token function">upper_bound</span><span class="token punctuation">(</span>s<span class="token operator">+</span>l<span class="token punctuation">,</span>s<span class="token operator">+</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>s<span class="token punctuation">[</span>l<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">-</span>s<span class="token punctuation">;</span>
        ans<span class="token operator">+=</span><span class="token punctuation">(</span>r<span class="token operator">-</span>l<span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>r<span class="token operator">-</span>l<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>
        <span class="token comment">// cout&lt;&lt;s[l]&lt;&lt;' '&lt;&lt;l&lt;&lt;" "&lt;&lt;(r-l)*(r-l-1)/2&lt;&lt;endl;</span>
        l<span class="token operator">=</span>r<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld"</span><span class="token punctuation">,</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h2 id="e最小表达式">E：最小表达式</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200407084749602.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong> <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">111</span><span class="token operator">+</span><span class="token number">1</span></code></pre>
<strong>输出</strong> <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">22</span></code></pre> <strong>说明</strong>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">11</span><span class="token operator">+</span><span class="token number">11</span><span class="token operator">=</span><span class="token number">22</span></code></pre> <strong>输入</strong> <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">9998765432111</span></code></pre>
<strong>输出</strong> <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1112345678999</span></code></pre> <strong>输入</strong>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">12</span><span class="token operator">+</span><span class="token number">35</span></code></pre> <strong>输出</strong> <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">38</span></code></pre>
<strong>说明</strong> <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">25</span><span class="token operator">+</span><span class="token number">13</span> <span class="token operator">=</span> <span class="token number">38</span></code></pre> <strong>输入</strong>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">23984692</span><span class="token operator">+</span><span class="token number">238752</span><span class="token operator">+</span><span class="token number">2</span><span class="token operator">+</span><span class="token number">34</span><span class="token operator">+</span></code></pre> <strong>输出</strong> <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5461</span></code></pre>
<strong>说明</strong> <pre class="language-cpp" data-language="cpp"><code class="language-cpp">嗯，这个答案是可以得到的</code></pre></p>
<hr />
<p>首先找到这个字符串中<code>+</code>的数目，这个数目+1就是需要分出的数字<br />
然后我们考虑位数问题：</p>
<ol type="1">
<li>数字有20位，分成5组，那么每个数字均为4位要优于某个大于四位+某个小于四位</li>
<li>数字有21位，分成5组，那么就是一个数字为五位，另外四个均为四位</li>
</ol>
<p>最高位越小结果越小</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">int</span> len<span class="token punctuation">,</span>num<span class="token punctuation">[</span><span class="token number">500050</span><span class="token punctuation">]</span><span class="token punctuation">,</span>ans<span class="token punctuation">[</span><span class="token number">500050</span><span class="token punctuation">]</span><span class="token punctuation">,</span>cnt_up<span class="token punctuation">,</span>cnt_n<span class="token punctuation">;</span>
<span class="token keyword">char</span> tmp<span class="token punctuation">[</span><span class="token number">500050</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%s"</span><span class="token punctuation">,</span>tmp<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>tmp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">!=</span><span class="token char">'\0'</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>tmp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">>=</span><span class="token char">'1'</span><span class="token operator">&amp;&amp;</span>tmp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">&lt;=</span><span class="token char">'9'</span><span class="token punctuation">)</span>num<span class="token punctuation">[</span>cnt_n<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>tmp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token char">'0'</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> cnt_up<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">int</span> len_normal<span class="token operator">=</span>cnt_n<span class="token operator">/</span><span class="token punctuation">(</span>cnt_up<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">,</span>len_special<span class="token operator">=</span>cnt_n<span class="token operator">%</span><span class="token punctuation">(</span>cnt_up<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">sort</span><span class="token punctuation">(</span>num<span class="token punctuation">,</span>num<span class="token operator">+</span>cnt_n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>len_special<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>ans<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">+=</span>num<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>

    <span class="token keyword">int</span> cur<span class="token operator">=</span>len_special<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>len_normal<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>cnt_up<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            ans<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+=</span>num<span class="token punctuation">[</span>cur<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">// cout&lt;&lt;"**"&lt;&lt;ans[i]&lt;&lt;"**"&lt;&lt;endl;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span>len_normal<span class="token punctuation">;</span>i<span class="token operator">>=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>ans<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">></span><span class="token number">9</span><span class="token punctuation">)</span>ans<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+=</span>ans<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">/</span><span class="token number">10</span><span class="token punctuation">,</span>ans<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>ans<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">%</span><span class="token number">10</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>ans<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">!=</span><span class="token number">0</span><span class="token punctuation">)</span>cout<span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>len_normal<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>cout<span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h2 id="f树上博弈">F：树上博弈</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200407085603355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">3</span>
<span class="token number">1</span> <span class="token number">2</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">2</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">当且仅当牛牛在<span class="token number">1</span>号点，牛妹在<span class="token number">3</span>号点，或者牛牛在<span class="token number">3</span>号点，牛妹在<span class="token number">1</span>号点时，牛牛才获胜。</code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">2</span>
<span class="token number">1</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">0</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">由于无论如何牛牛都无路可走，因此必然牛妹获胜。</code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">30</span>
<span class="token number">1</span> <span class="token number">1</span> <span class="token number">2</span> <span class="token number">1</span> <span class="token number">2</span> <span class="token number">1</span> <span class="token number">3</span> <span class="token number">2</span> <span class="token number">3</span> <span class="token number">4</span> <span class="token number">2</span> <span class="token number">3</span> <span class="token number">1</span> <span class="token number">2</span> <span class="token number">3</span> <span class="token number">4</span> <span class="token number">2</span> <span class="token number">4</span> <span class="token number">5</span> <span class="token number">6</span> <span class="token number">3</span> <span class="token number">4</span> <span class="token number">12</span> <span class="token number">12</span> <span class="token number">12</span> <span class="token number">13</span> <span class="token number">13</span> <span class="token number">13</span> <span class="token number">13</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">428</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">QwQ</code></pre>
<hr />
<p>我们设两人距离为d
那么一个人走一步，另一个人走一步，最后他们的距离一定为d或d-2或d+2，所以d奇偶性是不变的，经过无数字运动，一定会出现一种情况，牛妹进入了一个子树，但是唯一的出口被牛牛堵了，也就是牛妹进入了死胡同
牛妹必然会最终移动到叶子上。同样，如果最初D是奇数，则牛妹获胜。
因此，答案取决于距离的奇偶性：如果是偶数，则牛牛获胜，否则牛妹获胜。</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">ll</span> <span class="token expression"><span class="token keyword">long</span> <span class="token keyword">long</span></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">int</span> MAX_N<span class="token operator">=</span><span class="token number">1e6</span><span class="token operator">+</span><span class="token number">50</span><span class="token punctuation">;</span>
ll p<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">,</span>eid<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>deep_j<span class="token punctuation">,</span>deep_o<span class="token punctuation">,</span>n<span class="token punctuation">;</span>
<span class="token keyword">struct</span> <span class="token class-name">edge</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> v<span class="token punctuation">,</span>next<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>E<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    eid<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token function">memset</span><span class="token punctuation">(</span>p<span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">void</span> <span class="token function">insert</span><span class="token punctuation">(</span><span class="token keyword">int</span> u<span class="token punctuation">,</span><span class="token keyword">int</span> v<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    E<span class="token punctuation">[</span>eid<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token operator">=</span>p<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">;</span>
    E<span class="token punctuation">[</span>eid<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token operator">=</span>v<span class="token punctuation">;</span>
    p<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token operator">=</span>eid<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">void</span> <span class="token function">dfs</span><span class="token punctuation">(</span><span class="token keyword">int</span> node<span class="token punctuation">,</span><span class="token keyword">int</span> deep<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>deep<span class="token operator">%</span><span class="token number">2</span><span class="token punctuation">)</span>deep_j<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token keyword">else</span> deep_o<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span>p<span class="token punctuation">[</span>node<span class="token punctuation">]</span><span class="token punctuation">;</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">=</span>E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token function">dfs</span><span class="token punctuation">(</span>E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">,</span>deep<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> t<span class="token punctuation">;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>t<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">insert</span><span class="token punctuation">(</span>t<span class="token punctuation">,</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">dfs</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span>deep_j<span class="token operator">*</span><span class="token punctuation">(</span>deep_j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">+</span>deep_o<span class="token operator">*</span><span class="token punctuation">(</span>deep_o<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h2 id="g音乐鉴赏">G：音乐鉴赏</h2>
<p><img
src="https://img-blog.csdnimg.cn/2020040709405610.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong> <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">10</span>
<span class="token number">99</span> <span class="token number">99</span> <span class="token number">99</span> <span class="token number">99</span> <span class="token number">99</span> <span class="token number">99</span> <span class="token number">99</span> <span class="token number">99</span> <span class="token number">99</span> <span class="token number">99</span></code></pre>
<strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">50.00</span><span class="token operator">%</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">需要随机占比<span class="token number">50</span><span class="token operator">%</span>。</code></pre>
<hr />
<p>首先解释一下官方题解的意思 <img
src="https://img-blog.csdnimg.cn/20200407094234884.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /></p>
<ol type="1">
<li><p>Q: 这里的-y不应该是(y-90)吗？<br />
A: 确实是，但是可以发现，因为<span class="math inline">\(y \in
[0,90]\)</span>所以y-90
均匀的分布在[-90,0]这与-y的分布式相同的，所以写了-y简便运算</p></li>
<li><p>Q: E是怎么推出来的?<br />
A: 在上一个式子中，带入y=90，得到<span
class="math inline">\(\frac{(sorce-90)*(1-x)}{90x} \geq
1\)</span>，如果一个一个分数满足题意，他的<span
class="math inline">\(\frac{(sorce-90)*1-x}{90x} \geq
1\)</span>，从<strong>数学期望</strong>上说，10%的人优秀，相当于0.1*n的人均下来要恰好=1
这就有了E式</p></li>
</ol>
<p>实际上不必那么麻烦，我们可以按自己思路写下去 <span
class="math display">\[
sorce*(1-x)+xy \geq 90 \\
\frac{sorce*(1-x)-90} {-x} \leq y\\
\]</span> 小于等于90的概率是 <span class="math display">\[
\frac{sorce*(1-x)-90} {-90x}\\
\]</span> 大于等于90的概率是 <span class="math display">\[
1-\frac{sorce*(1-x)-90} {-90x}\\
\frac{90x-90+sorce*(1-x)} {90x}\\
\]</span> 于是 <span class="math display">\[
\sum_{i=1}^{n}\frac{90x-90+sorce*(1-x)} {90x} = 0.1n
\]</span></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> n<span class="token punctuation">,</span>sumn<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    cin<span class="token operator">>></span>n<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> t<span class="token punctuation">;</span>
        cin<span class="token operator">>></span>t<span class="token punctuation">;</span>
        sumn<span class="token operator">+=</span>t<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">double</span> s2<span class="token operator">=</span><span class="token punctuation">(</span>sumn<span class="token operator">-</span><span class="token number">90</span><span class="token operator">*</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%.2f%%"</span><span class="token punctuation">,</span><span class="token punctuation">(</span>s2<span class="token operator">/</span><span class="token punctuation">(</span><span class="token number">9</span><span class="token operator">*</span>n<span class="token operator">+</span>s2<span class="token punctuation">)</span><span class="token operator">*</span><span class="token number">100</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h2 id="h-坐火车">H: 坐火车</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200407101404442.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span>
<span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span></code></pre>
<p>输出</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">0</span> <span class="token number">3</span> <span class="token number">4</span> <span class="token number">3</span> <span class="token number">0</span></code></pre>
<hr />
<p>考虑构建一个数组记录某个颜色在<strong>当前状态(下标)</strong>
下，位置左边有多少个该颜色火车(sum_l[color])，右边有多少个火车(sum_r[color])，构建的这个数组随着当前数组下标位置的改变而改变<br />
在构建一个前缀和，记录某个颜色在<strong>当前状态(下标)</strong>
左乘右的值(也就是贡献值)，这样，对于每一次查询我们只需要做一个差就可以了，我们用树状数组实现它<br />
对于一次状态(数组下标)的移动(<strong>以从红色移到蓝色为例</strong>)，发生的变化是</p>
<ol type="1">
<li>红色作左边的个数+1(sum_l[红色]++)</li>
<li>这个红色可以和右边的红色匹配，所以红色贡献值+=sum_r[红色]</li>
<li>蓝色作右边的个数-1(sum_r[蓝色]--)</li>
<li>这个蓝色失去了和左边的蓝色的匹配，所以蓝色贡献值-=sum_l[蓝色]</li>
</ol>
<p>注意的是第一次是没有12步骤的，因为刚刚移动到第一节火车</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">int</span> MAX_N<span class="token operator">=</span><span class="token number">5e5</span><span class="token operator">+</span><span class="token number">50</span><span class="token punctuation">;</span>

<span class="token keyword">long</span> <span class="token keyword">long</span> sum_l<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">,</span>sum_r<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">,</span>s<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">,</span>n<span class="token punctuation">,</span>col<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">,</span>col_l<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">,</span>col_r<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">,</span><span class="token keyword">int</span> v<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span>x<span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>MAX_N<span class="token punctuation">;</span>i<span class="token operator">+=</span>i<span class="token operator">&amp;</span><span class="token punctuation">(</span><span class="token operator">-</span>i<span class="token punctuation">)</span><span class="token punctuation">)</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+=</span>v<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> res<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span>x<span class="token punctuation">;</span>i<span class="token punctuation">;</span>i<span class="token operator">-=</span>i<span class="token operator">&amp;</span><span class="token punctuation">(</span><span class="token operator">-</span>i<span class="token punctuation">)</span><span class="token punctuation">)</span>res<span class="token operator">+=</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>col<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>col_l<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>col_r<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        sum_r<span class="token punctuation">[</span>col<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        sum_r<span class="token punctuation">[</span>col<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">--</span><span class="token punctuation">;</span>
        <span class="token function">add</span><span class="token punctuation">(</span>col<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token operator">-</span>sum_l<span class="token punctuation">[</span>col<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d "</span><span class="token punctuation">,</span><span class="token function">query</span><span class="token punctuation">(</span>col_r<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token function">query</span><span class="token punctuation">(</span>col_l<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">continue</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        sum_l<span class="token punctuation">[</span>col<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span>
        <span class="token function">add</span><span class="token punctuation">(</span>col<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span>sum_r<span class="token punctuation">[</span>col<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld "</span><span class="token punctuation">,</span><span class="token function">query</span><span class="token punctuation">(</span>col_r<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token function">query</span><span class="token punctuation">(</span>col_l<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h2 id="i-匹配星星">I: 匹配星星</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200407102724900.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">2</span>
<span class="token number">1</span> <span class="token number">1</span> <span class="token number">0</span>
<span class="token number">2</span> <span class="token number">2</span> <span class="token number">1</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1</span></code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">2</span>
<span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span>
<span class="token number">2</span> <span class="token number">2</span> <span class="token number">1</span></code></pre>
<p>输出</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">0</span></code></pre>
<hr />
<p>我们构建一个可重复集合存放那些待配匹配的星星，他们的z一定是0，这样读取到z=1的星星的时候我们就拿z=1的星星尝试和他们匹配<br />
在处理星星的时候我们遵循以下顺序<br />
x小的优先读取，这样保证后读的星星x一定大，这样我准备去匹配的z=1星星一定比在待匹配集合中的星星x大，z大<br />
匹配时我们的xz都比集合中的星星大，我们只要找y比匹配星星小的即可，那选哪个呢？选比匹配星星的y小的里面y最大的，这样，不仅满足了这次匹配，也为下次匹配创建了最大的机会<br />
这么找这个星星呢？<br />
可以使用upper_bound.<br />
upper_bound在一般情况下是找严格大于一个数的第一个数据
所以我们可以重载&lt;从而实现找到严格小于这个数据的第一个数据，<a
target="_blank" rel="noopener" href="https://blog.csdn.net/Liukairui/article/details/104602907">看这里</a><br />
可重复集合使用multiset即可实现，multiset<strong>自带</strong>一个upper_bounder的方法，<strong>用这个不需要指定查找范围</strong><br />
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;set></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">int</span> MAX_N<span class="token operator">=</span><span class="token number">1e5</span><span class="token operator">+</span><span class="token number">50</span><span class="token punctuation">;</span>

<span class="token keyword">struct</span> <span class="token class-name">star</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> x<span class="token punctuation">,</span>y<span class="token punctuation">,</span>z<span class="token punctuation">;</span>

    <span class="token keyword">bool</span> <span class="token keyword">operator</span> <span class="token operator">&lt;</span> <span class="token punctuation">(</span><span class="token keyword">const</span> star t<span class="token punctuation">)</span><span class="token keyword">const</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">return</span> y<span class="token operator">></span>t<span class="token punctuation">.</span>y<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

<span class="token punctuation">&#125;</span>a<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">bool</span> <span class="token function">cmp</span><span class="token punctuation">(</span>star a<span class="token punctuation">,</span>star b<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">return</span> a<span class="token punctuation">.</span>x<span class="token operator">==</span>b<span class="token punctuation">.</span>x<span class="token operator">?</span>a<span class="token punctuation">.</span>z<span class="token operator">></span>b<span class="token punctuation">.</span>z<span class="token operator">:</span>a<span class="token punctuation">.</span>x<span class="token operator">&lt;</span>b<span class="token punctuation">.</span>x<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

multiset<span class="token operator">&lt;</span>star<span class="token operator">></span>s<span class="token punctuation">;</span>     <span class="token comment">//s</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> n<span class="token punctuation">,</span>ans<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>x<span class="token punctuation">,</span><span class="token operator">&amp;</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>y<span class="token punctuation">,</span><span class="token operator">&amp;</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>z<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">sort</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span>a<span class="token operator">+</span>n<span class="token punctuation">,</span>cmp<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>z<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span>s<span class="token punctuation">.</span><span class="token function">insert</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">auto</span> it<span class="token operator">=</span>s<span class="token punctuation">.</span><span class="token function">upper_bound</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>it<span class="token operator">!=</span>s<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                s<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span>it<span class="token punctuation">)</span><span class="token punctuation">;</span>
                ans<span class="token operator">++</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre></p>
<h2 id="j-二维跑步">J: 二维跑步</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200407103758117.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span> <span class="token number">2</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5616</span></code></pre>
<hr />
<figure>
<img
src="https://img-blog.csdnimg.cn/20200407103947641.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" />
<figcaption aria-hidden="true">在这里插入图片描述</figcaption>
</figure>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
 
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">typedef</span> <span class="token keyword">long</span> <span class="token keyword">long</span> ll<span class="token punctuation">;</span>
<span class="token keyword">int</span> mod <span class="token operator">=</span> <span class="token number">998244353</span><span class="token punctuation">;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">sq</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token keyword">return</span> <span class="token number">1ll</span><span class="token operator">*</span>x<span class="token operator">*</span>x<span class="token operator">%</span>mod<span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">sub</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span><span class="token keyword">int</span> b<span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token keyword">return</span> a<span class="token operator">&lt;</span>b<span class="token operator">?</span>a<span class="token operator">-</span>b<span class="token operator">+</span>mod<span class="token operator">:</span>a<span class="token operator">-</span>b<span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span><span class="token keyword">int</span> b<span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token keyword">return</span> a<span class="token operator">+</span>b<span class="token operator">>=</span>mod<span class="token operator">?</span>a<span class="token operator">+</span>b<span class="token operator">-</span>mod<span class="token operator">:</span>a<span class="token operator">+</span>b<span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">mul</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span><span class="token keyword">int</span> b<span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token keyword">return</span> <span class="token number">1ll</span><span class="token operator">*</span>a<span class="token operator">*</span>b<span class="token operator">%</span>mod<span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">pow</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span><span class="token keyword">int</span> b<span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token keyword">if</span><span class="token punctuation">(</span>b <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span><span class="token keyword">return</span> b<span class="token operator">&amp;</span><span class="token number">1</span><span class="token operator">?</span><span class="token function">mul</span><span class="token punctuation">(</span><span class="token function">sq</span><span class="token punctuation">(</span><span class="token function">pow</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span>b<span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">,</span>a<span class="token punctuation">)</span><span class="token operator">:</span><span class="token function">sq</span><span class="token punctuation">(</span><span class="token function">pow</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span>b<span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> N <span class="token operator">=</span> <span class="token number">3000010</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> G<span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">,</span>fac<span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">,</span>invfac<span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">,</span>pow2<span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">,</span>pow3<span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">,</span>n<span class="token punctuation">,</span>m<span class="token punctuation">;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">C</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">,</span><span class="token keyword">int</span> m<span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token keyword">return</span> <span class="token function">mul</span><span class="token punctuation">(</span>fac<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token function">mul</span><span class="token punctuation">(</span>invfac<span class="token punctuation">[</span>m<span class="token punctuation">]</span><span class="token punctuation">,</span>invfac<span class="token punctuation">[</span>n<span class="token operator">-</span>m<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
 
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">F</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">,</span><span class="token keyword">int</span> m<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>m<span class="token operator">></span>n <span class="token operator">||</span> m<span class="token operator">&lt;</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token function">mul</span><span class="token punctuation">(</span><span class="token function">mul</span><span class="token punctuation">(</span>fac<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token function">mul</span><span class="token punctuation">(</span>invfac<span class="token punctuation">[</span>m<span class="token punctuation">]</span><span class="token punctuation">,</span>invfac<span class="token punctuation">[</span>n<span class="token operator">-</span>m<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token function">mul</span><span class="token punctuation">(</span>pow2<span class="token punctuation">[</span>n<span class="token operator">-</span>m<span class="token punctuation">]</span><span class="token punctuation">,</span>pow3<span class="token punctuation">[</span>m<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    fac<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> pow2<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> pow3<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>N<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        fac<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1ll</span><span class="token operator">*</span>fac<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">*</span>i<span class="token operator">%</span>mod<span class="token punctuation">;</span>
        pow2<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1ll</span><span class="token operator">*</span>pow2<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">*</span><span class="token number">2</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
        pow3<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1ll</span><span class="token operator">*</span>pow3<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">*</span><span class="token number">3</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    invfac<span class="token punctuation">[</span>N<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">pow</span><span class="token punctuation">(</span>fac<span class="token punctuation">[</span>N<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span>mod<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span>N<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">;</span>i<span class="token operator">>=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">)</span> invfac<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1ll</span><span class="token operator">*</span>invfac<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">*</span><span class="token punctuation">(</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    cin<span class="token operator">>></span>n<span class="token operator">>></span>m<span class="token punctuation">;</span>
    G<span class="token punctuation">[</span>n<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> upb <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span>lwb <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span>ans <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> move<span class="token operator">=</span>n<span class="token punctuation">;</span>move<span class="token operator">>=</span><span class="token number">0</span><span class="token punctuation">;</span>move<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> nlwb <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token operator">-</span>m<span class="token operator">+</span>n<span class="token operator">-</span>move<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">,</span>nupb <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span><span class="token punctuation">(</span>m<span class="token operator">+</span>n<span class="token operator">-</span>move<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">,</span>n<span class="token operator">-</span>move<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>lwb<span class="token operator">&lt;</span>nlwb<span class="token punctuation">)</span>ans <span class="token operator">=</span> <span class="token function">sub</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">F</span><span class="token punctuation">(</span>n<span class="token operator">-</span>move<span class="token punctuation">,</span>lwb<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">,</span>lwb<span class="token operator">++</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>lwb<span class="token operator">></span>nlwb<span class="token punctuation">)</span>lwb<span class="token operator">--</span><span class="token punctuation">,</span>ans <span class="token operator">=</span> <span class="token function">add</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">F</span><span class="token punctuation">(</span>n<span class="token operator">-</span>move<span class="token punctuation">,</span>lwb<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>upb<span class="token operator">&lt;</span>nupb<span class="token punctuation">)</span>upb<span class="token operator">++</span><span class="token punctuation">,</span>ans <span class="token operator">=</span> <span class="token function">add</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">F</span><span class="token punctuation">(</span>n<span class="token operator">-</span>move<span class="token punctuation">,</span>upb<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>upb<span class="token operator">></span>nupb<span class="token punctuation">)</span>ans <span class="token operator">=</span> <span class="token function">sub</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">F</span><span class="token punctuation">(</span>n<span class="token operator">-</span>move<span class="token punctuation">,</span>upb<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">,</span>upb<span class="token operator">--</span><span class="token punctuation">;</span>
        G<span class="token punctuation">[</span>move<span class="token punctuation">]</span> <span class="token operator">=</span> ans<span class="token punctuation">;</span>
        ans <span class="token operator">=</span> <span class="token function">mul</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        ans <span class="token operator">=</span> <span class="token function">add</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">mul</span><span class="token punctuation">(</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token function">F</span><span class="token punctuation">(</span>n<span class="token operator">-</span>move<span class="token punctuation">,</span>lwb<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        ans <span class="token operator">=</span> <span class="token function">add</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">mul</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token function">F</span><span class="token punctuation">(</span>n<span class="token operator">-</span>move<span class="token punctuation">,</span>upb<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        upb<span class="token operator">+=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span>n<span class="token punctuation">;</span>i<span class="token operator">>=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token function">add</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">mul</span><span class="token punctuation">(</span>G<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token function">C</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span>i<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span>ans<span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>

    </div>

    
    
    
      


    <footer class="post-footer">
          <div class="reward-container">
  <div></div>
  <button>
    赞赏
  </button>
  <div class="post-reward">
      <div>
        <img src="/images/wechatpay.png" alt="Liu Kairui 微信">
        <span>微信</span>
      </div>
      <div>
        <img src="/images/alipay.png" alt="Liu Kairui 支付宝">
        <span>支付宝</span>
      </div>

  </div>
</div>

          

<div class="post-copyright">
<ul>
  <li class="post-copyright-author">
      <strong>本文作者： </strong>Liu Kairui
  </li>
  <li class="post-copyright-link">
      <strong>本文链接：</strong>
      <a href="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A54%E9%A2%98%E8%A7%A3/" title="2020牛客寒假算法基础集训营4题解">http://liukairui.me/article/2020牛客寒假算法基础集训营4题解/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" rel="noopener" target="_blank"><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处！
  </li>
</ul>
</div>

          <div class="post-tags">
              <a href="/tags/%E7%AE%97%E6%B3%95/" rel="tag"><i class="fa fa-tag"></i> 算法</a>
              <a href="/tags/%E7%89%9B%E5%AE%A2/" rel="tag"><i class="fa fa-tag"></i> 牛客</a>
              <a href="/tags/ACM/" rel="tag"><i class="fa fa-tag"></i> ACM</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/article/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-%E6%95%B0%E4%BD%8DDP/" rel="prev" title="动态规划-数位DP">
                  <i class="fa fa-chevron-left"></i> 动态规划-数位DP
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A55%E9%A2%98%E8%A7%A3/" rel="next" title="2020牛客寒假算法基础集训营5题解">
                  2020牛客寒假算法基础集训营5题解 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






    <div class="comments" id="valine-comments"></div>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 2019 – 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Liu Kairui</span>
</div>
<div class="busuanzi-count">
    <span class="post-meta-item" id="busuanzi_container_site_uv">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-item" id="busuanzi_container_site_pv">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" rel="noopener" target="_blank">NexT.Muse</a> 强力驱动
  </div>
  <div class="addthis_inline_share_toolbox">
    <script src="//s7.addthis.com/js/300/addthis_widget.js#pubid=ra-6231eb6f709fc868" async="async"></script>
  </div><script
  async
  src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"
></script>

 
<script src="https://cdn.jsdelivr.net/npm/moment@2.22.2/moment.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/moment-precise-range-plugin@1.3.0/moment-precise-range.min.js"></script>
<script>
  function timer() {
    var ages = moment.preciseDiff(moment(),moment(20201101,"YYYYMMDD"));
    ages = ages.replace(/years?/, "年");
    ages = ages.replace(/months?/, "月");
    ages = ages.replace(/days?/, "天");
    ages = ages.replace(/hours?/, "小时");
    ages = ages.replace(/minutes?/, "分");
    ages = ages.replace(/seconds?/, "秒");
    ages = ages.replace(/\d+/g, '<span class="daysCnt" style="color:#1890ff">$&</span>');
    div.innerHTML = `我已在此等候你 ${ages}`;
    div.className="workDays";
  }
  var div = document.createElement("div");
  //插入到copyright之后
  var copyright = document.querySelector(".copyright");
  document.querySelector(".footer-inner").insertBefore(div, copyright.nextSibling);
  timer();
  setInterval("timer()",1000)
</script>



    </div>
  </footer>

  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/@next-theme/pjax@0.5.0/pjax.min.js" integrity="sha256-3NkoLDrmHLTYj7csHIZSr0MHAFTXth7Ua/DDt4MRUAg=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.6.0/jquery.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.js" integrity="sha256-yt2kYMy0w8AbtF89WXb2P1rfjcP/HTHLT7097U8Y5b8=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/lozad.js/1.16.0/lozad.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/pangu/4.0.7/pangu.min.js"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  
<script src="https://cdn.jsdelivr.net/npm/hexo-generator-searchdb@1.4.0/dist/search.js" integrity="sha256-vXZMYLEqsROAXkEw93GGIvaB2ab+QW6w3+1ahD9nXXA=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>


  <script class="next-config" data-name="mermaid" type="application/json">{"enable":true,"theme":"forest","js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mermaid/8.14.0/mermaid.min.js","integrity":"sha256-7wT34TI0pEBeEFoi4z+vhuSddGh6vUTMWdqJ2SDe2jg="}}</script>
  <script src="/js/third-party/tags/mermaid.js"></script>

  <script src="/js/third-party/fancybox.js"></script>

  <script src="/js/third-party/pace.js"></script>

  
  <script data-pjax async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>


  <script class="next-config" data-name="leancloud_visitors" type="application/json">{"enable":true,"app_id":"ABKlVtS4cyaWYEwunPyK3sXt-9Nh9j0Va","app_key":"xxGXdTTEGEVifs2TLB35844I","server_url":"https://abklvts4.lc-cn-e1-shared.com","security":false}</script>
  <script src="/js/third-party/statistics/lean-analytics.js"></script>


  

  <script class="next-config" data-name="enableMath" type="application/json">true</script><script class="next-config" data-name="mathjax" type="application/json">{"enable":true,"tags":"none","mhchem":true,"js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.0/es5/tex-mml-chtml.min.js"}}</script>
<script src="/js/third-party/math/mathjax.js"></script>


  <script src="https://cdnjs.cloudflare.com/ajax/libs/quicklink/2.2.0/quicklink.umd.js" integrity="sha256-4kQf9z5ntdQrzsBC3YSHnEz02Z9C1UeW/E9OgnvlzSY=" crossorigin="anonymous"></script>
  <script class="next-config" data-name="quicklink" type="application/json">{"enable":true,"home":false,"archive":false,"delay":true,"timeout":3000,"priority":true,"url":"http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A54%E9%A2%98%E8%A7%A3/"}</script>
  <script src="/js/third-party/quicklink.js"></script>
<script src="https://cdn.jsdelivr.net/npm/darkmode-js@1.5.7/lib/darkmode-js.min.js"></script>

<script>
var options = {
  bottom: '64px',
  right: 'unset',
  left: '32px',
  time: '0.5s',
  mixColor: 'transparent',
  backgroundColor: 'transparent',
  buttonColorDark: '#100f2c',
  buttonColorLight: '#fff',
  saveInCookies: true,
  label: '🌓',
  autoMatchOsTheme: true
}
const darkmode = new Darkmode(options);
window.darkmode = darkmode;
darkmode.showWidget();
</script>


<script class="next-config" data-name="valine" type="application/json">{"enable":true,"appId":"ABKlVtS4cyaWYEwunPyK3sXt-9Nh9j0Va","appKey":"xxGXdTTEGEVifs2TLB35844I","serverURLs":"https://abklvts4.lc-cn-e1-shared.com","placeholder":"请开始你的表演","avatar":"identicon","meta":["nick","mail","link"],"pageSize":10,"lang":"zh-CN","visitor":false,"comment_count":true,"recordIP":true,"enableQQ":true,"requiredFields":[],"el":"#valine-comments","path":"/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A54%E9%A2%98%E8%A7%A3/"}</script>
<script>
document.addEventListener('page:loaded', () => {
  NexT.utils.loadComments(CONFIG.valine.el)
    .then(() => NexT.utils.getScript(
      'https://cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js',
      { condition: window.Valine }
    ))
    .then(() => {
      new Valine(CONFIG.valine);
    });
});
</script>


  <script async src="/js/fireworks.js"></script>




  <script src="/js/activate-power-mode.min.js"></script>
  <script>
    POWERMODE.colorful = true;
    POWERMODE.shake = false;
    document.body.addEventListener('input', POWERMODE);
  </script>




  <script src="/js/wobblewindow.js"></script>
  <script>
    //只在桌面版网页启用特效 记得同步到header.njk
    if( window.innerWidth > 768  ){
      $(document).ready(function () {
        
          $('body>main>header').wobbleWindow({
            radius: 50,
            movementTop: false,
            movementLeft: false,
            movementRight: false,
            debug: false,
          });
        

        //
        //  $('body header>aside').wobbleWindow({
        //    radius: 50,
        //    movementLeft: false,
        //    movementTop: false,
        //    movementBottom: false,
        //    position: 'fixed',
        //    debug: false,
        //  });
        //

        
          $('body>footer').wobbleWindow({
            radius: 50,
            movementBottom: false,
            movementLeft: false,
            movementRight: false,
            debug: false,
          });
        
      });
    }
  </script>


 
<script>
  $(document).ready(function(){
    var beian = document.querySelector(".footer-inner > .beian > a");
    var cpr=document.querySelector(".footer-inner > .copyright");
    var cnz=document.querySelector(".workDays");//.parentNode;
    var bsz=document.querySelector(".busuanzi-count");
    if(cnz!=null&&bsz!=null)
      cnz.parentNode.insertBefore(bsz,cnz);
    if(bsz == null || bsz == undefined || document.querySelector("#busuanzi_value_site_pv").innerText=="" || document.querySelector("#busuanzi_value_site_uv").innerText == "")
      bsz.remove();
    checkIndex();
    if(beian){cpr.classList.add('split-line');cpr.appendChild(beian);}
  })
  $(document).on('pjax:complete',checkIndex);
</script>



<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"log":false,"model":{"jsonPath":"/live2dw/assets/hijiki.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":false},"react":{"opacity":0.7}});</script></body>
</html>
